Overview

Suppose matrix N×NN\times N matrix, AA, which is real symmetric or complex Hermitian, and positive semidefinite. Then, for an arbitrary N×kN \times k test matrix Ω\Omega, define the Nyström approximation to be

Aˆnys=A⟨Ω⟩:=AΩ(Ω∗AΩ)†Ω∗A\hat{A}_\text{nys} = A \langle \Omega \rangle := A \Omega (\Omega^* A \Omega)^{\dagger} \Omega^* A

(note: for a matrix MM, can replace Moore-Penrose pseudoinverse M†M^\dagger with M−1M^{-1} matrix inverse if MM is invertible; M∗M^* denotes conjugate transpose)

or in terms of sketch matrix Y=AΩY = A \Omega,

A⟨Ω⟩=Y(Ω∗Y)†Y∗A \langle \Omega \rangle = Y (\Omega^* Y)^{\dagger} Y^*

Notes

  • (why do this?) obtains a kk-rank approximation (low-rank approximation)

References

  1. https://andrewcharlesjones.github.io/journal/nystrom-approximation.html
  2. https://www.ethanepperly.com/index.php/2022/10/11/low-rank-approximation-toolbox-nystrom-approximation/
  3. R. Xu and Y. Lu, “What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?,” May 22, 2025, arXiv: arXiv:2502.07993. doi: 10.48550/arXiv.2502.07993.